"""
题目：https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
    示例 1：
    输入：l1 = [1,2,4], l2 = [1,3,4]
    输出：[1,1,2,3,4,4]
思路：迭代法。当l1和l2都不是空链表时，比较两个链表的大小，将小的值传递给结果，并将小的链表结点后移一位。
时间复杂度：O(m+n)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:  
        cur = ListNode(0)
        pre = cur   
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
            
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
        return pre.next